{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ugly Number II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #dynamic-programming #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #动态规划 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nthUglyNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #丑数 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，请你找出并返回第 <code>n</code> 个 <strong>丑数</strong> 。</p>\n",
    "\n",
    "<p><strong>丑数 </strong>就是质因子只包含&nbsp;<code>2</code>、<code>3</code> 和&nbsp;<code>5</code>&nbsp;的正整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>1 通常被视为丑数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1690</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ugly-number-ii](https://leetcode.cn/problems/ugly-number-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ugly-number-ii](https://leetcode.cn/problems/ugly-number-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        a,b,c = 0,0,0\n",
    "        dp = [1]*n\n",
    "        for i in range(1,n):\n",
    "            x,y,z = dp[a]*2,dp[b]*3,dp[c]*5\n",
    "            dp[i] = min(x,y,z)\n",
    "            if dp[i] == x:\n",
    "                a+=1\n",
    "            if dp[i] == y:\n",
    "                b+=1\n",
    "            if dp[i] == z:\n",
    "                c+=1\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res  = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]\n",
    "        rs  = set(res)\n",
    "        i = 0\n",
    "        chou = [2,3,5]\n",
    "        while len(rs)<n*4:\n",
    "            cl = len(res)\n",
    "            new_res = []\n",
    "            for j in range(i,len(res)):\n",
    "                for k in chou:\n",
    "                    curr = res[j]*k\n",
    "                    if curr not in rs:\n",
    "                        rs.add(curr)\n",
    "                        new_res.append(curr)  \n",
    "            #new_res.sort()\n",
    "            res.extend(new_res)\n",
    "        res.sort()\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        a = b = c =0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5\n",
    "            dp[i] = min(n2,n3,n5)\n",
    "            if dp[i]==n2:\n",
    "                a = a + 1\n",
    "            if dp[i]==n3:\n",
    "                b = b + 1\n",
    "            if dp[i]==n5:\n",
    "                c = c + 1\n",
    "\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res=[1]*n\n",
    "        a,b,c=0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2:\n",
    "                a += 1\n",
    "            if res[i] == n3:\n",
    "                b += 1\n",
    "            if res[i] == n5:\n",
    "                c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0, 1]\n",
    "        p2 = p3 = p5 = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            dp.append(min(dp[p2]*2, dp[p3]*3, dp[p5]*5))\n",
    "            if dp[-1] == dp[p2] * 2:\n",
    "                p2 += 1\n",
    "            if dp[-1] == dp[p3] * 3:\n",
    "                p3 += 1\n",
    "            if dp[-1] == dp[p5] * 5:\n",
    "                p5 += 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "Min Heap\n",
    "\n",
    "T: O(N logN)\n",
    "S: O(N)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = [2, 3, 5]\n",
    "        minheap = [1]   # first node in min-heap is 1\n",
    "\n",
    "        for _ in range(n):\n",
    "            curr = heappop(minheap)\n",
    "            for factor in factors:\n",
    "                heappush(minheap, curr*factor)\n",
    "                if curr % factor == 0:\n",
    "                    break\n",
    "\n",
    "        return curr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        stack = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]\n",
    "        fa = [2,3,5]\n",
    "        if n <= 10:return stack[n-1]\n",
    "        t = n-10\n",
    "        for _ in range(t):\n",
    "            top = stack[-1]\n",
    "            nex = [inf]*3\n",
    "            for j,y in enumerate(fa):\n",
    "                for x in stack:\n",
    "                    if x*y > top:\n",
    "                        nex[j] = x*y\n",
    "                        break\n",
    "            minnex = min(nex)\n",
    "            stack.append(minnex)\n",
    "        #print(stack)\n",
    "        return stack[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # dp[i] 表示第i个丑数\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[1] = 1\n",
    "        p2, p3, p5 = 1, 1, 1\n",
    "        for i in range(2, n+1):\n",
    "            dp2 = dp[p2] * 2\n",
    "            dp3 = dp[p3] * 3\n",
    "            dp5 = dp[p5] * 5\n",
    "            cur = min(min(dp2, dp3), dp5)\n",
    "            if cur == dp2:\n",
    "                p2 += 1\n",
    "            if cur == dp3:\n",
    "                p3 += 1\n",
    "            if cur == dp5:\n",
    "                p5 += 1\n",
    "            dp[i] = cur\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [1]*n\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = res[a] * 2,res[b] * 3 ,res[c] * 5\n",
    "            res[i] = min(n2,n3,n5)\n",
    "            if res[i] == n2:\n",
    "                a += 1\n",
    "            if res[i] == n3:\n",
    "                b += 1\n",
    "            if res[i] == n5:\n",
    "                c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nthUglyNumber(self, n: int) -> int:\n",
    "#         factors = [2, 3, 5]\n",
    "#         seen = [1]\n",
    "#         heap = [1]\n",
    "\n",
    "#         for _ in range(1, n):\n",
    "#             curr = heapq.heappop(heap)\n",
    "#             for factor in factors:\n",
    "#                 nxt = curr * factor\n",
    "#                 if nxt not in seen:\n",
    "#                     seen.append(nxt)\n",
    "#                     heapq.heappush(heap, nxt)\n",
    "        \n",
    "#         return heapq.heappop(heap)\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res, a, b, c = [1] * n, 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        idx_table = [0,0,0]\n",
    "        x2,x3,x5 = 2,3,5\n",
    "        ug_number = [1]\n",
    "        while(n>1):\n",
    "            min_x = min(x2,x3,x5)\n",
    "            ug_number.append(min_x)\n",
    "            if x2==min_x:\n",
    "                idx_table[0]+=1\n",
    "                x2 = ug_number[idx_table[0]]*2\n",
    "            if x3==min_x:\n",
    "                idx_table[1]+=1\n",
    "                x3 = ug_number[idx_table[1]]*3\n",
    "            if x5==min_x:\n",
    "                idx_table[2]+=1\n",
    "                x5 = ug_number[idx_table[2]]*5\n",
    "            n-=1\n",
    "        return ug_number[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        a = [1]\n",
    "        for i in range(n):\n",
    "            x,y,z = a[p2]*2,a[p3]*3,a[p5]*5\n",
    "            minnum = min(x,y,z)\n",
    "            a.append(minnum)\n",
    "            if x == minnum:\n",
    "                p2+=1\n",
    "            if y ==minnum:\n",
    "                p3+=1\n",
    "            if z == minnum:\n",
    "                p5+=1\n",
    "        return a[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5\n",
    "            dp[i] = min(num2, num3, num5)\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        \n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "        for i in range(2, n + 1):\n",
    "            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5\n",
    "            dp[i] = min(num2, num3, num5)\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min(dp[a]*2, dp[b]*3, dp[c]*5)\n",
    "            if dp[i]==dp[a]*2:\n",
    "                a += 1\n",
    "            if dp[i]==dp[b]*3:\n",
    "                b += 1\n",
    "            if dp[i]==dp[c]*5:\n",
    "                c += 1\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n):\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5\n",
    "            dp[i]=min(n2,n3,n5)\n",
    "            if dp[i] == n2:\n",
    "                a+=1\n",
    "            if dp[i] == n3:\n",
    "                b+=1\n",
    "            if dp[i] == n5:\n",
    "                c+=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "        for i in range(2,n+1):\n",
    "            num2,num3,num5 = dp[p2] * 2,dp[p3] * 3,dp[p5] * 5\n",
    "            dp[i] = min(num2,num3,num5)\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3: #不能用else\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        a = [1]\n",
    "        for i in range(n):\n",
    "            x,y,z = a[p2]*2,a[p3]*3,a[p5]*5\n",
    "            minnum = min(x,y,z)\n",
    "            a.append(minnum)\n",
    "            if x == minnum:\n",
    "                p2+=1\n",
    "            if y ==minnum:\n",
    "                p3+=1\n",
    "            if z == minnum:\n",
    "                p5+=1\n",
    "        return a[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # 每一个丑数都可以通过之前的丑数x3，x5，x2得到\n",
    "        # 为了保证严重递增，每次都是生成之前的最小值\n",
    "        res = [1] * n\n",
    "        a, b, c = 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        \n",
    "        return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def minX(num1,num2,num3):\n",
    "    x = num1[0]\n",
    "    y = num2[0]\n",
    "    z = num3[0]\n",
    "    res = min(x,y,z)\n",
    "    if res ==x: num1 = num1[1:]\n",
    "    if res == y: num2 = num2[1:]\n",
    "    if res == z: num3 = num3[1:]\n",
    "\n",
    "    return num1, num2, num3, res\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n ==1: return 1\n",
    "        res = [1]\n",
    "        x = 1\n",
    "        add_num = None\n",
    "        num1 = [i*2 for i in res]\n",
    "        num2 = [i*3 for i in res]\n",
    "        num3 = [i*5 for i in res]\n",
    "        while x < n:\n",
    "            num1, num2, num3 , add_num = minX(num1, num2, num3)\n",
    "            res.append(add_num)\n",
    "            x += 1\n",
    "            num1.append(add_num*2)\n",
    "            num2.append(add_num*3)\n",
    "            num3.append(add_num*5)\n",
    "        return add_num\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res, a, b, c = [1]*n, 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        visited = defaultdict(lambda: False)\n",
    "        pq = [1]\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            c = heapq.heappop(pq)\n",
    "            for nxt in [c*2, c*3, c*5]:\n",
    "                if not visited[nxt]:\n",
    "                    visited[nxt] = True\n",
    "                    heapq.heappush(pq, nxt)\n",
    "\n",
    "        return pq[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        nums = [2, 3, 5]\n",
    "        heap = [1]\n",
    "        cur = 1\n",
    "        for i in range(n):\n",
    "            cur = heapq.heappop(heap)\n",
    "            for k in nums:\n",
    "                n = k * cur\n",
    "                if n not in heap:\n",
    "                    heapq.heappush(heap, k * cur)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        temp = [1]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        k = 0\n",
    "        z = 1\n",
    "        while z < n:\n",
    "            st = min(temp[i]*2, temp[j]*3, temp[k]*5)\n",
    "            if st == temp[i]*2:\n",
    "                i+=1\n",
    "            elif st == temp[j]*3:\n",
    "                j+=1\n",
    "            else:\n",
    "                k+=1\n",
    "            if st == temp[-1]:\n",
    "                continue\n",
    "            temp.append(st)\n",
    "            z+=1\n",
    "            \n",
    "        return temp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        l = [1]*n\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = l[a]*2,l[b]*3,l[c]*5\n",
    "            l[i] = min(n2,n3,n5)\n",
    "            if l[i] == n2:\n",
    "                a+=1\n",
    "            if l[i] == n3:\n",
    "                b+=1\n",
    "            if l[i] == n5:\n",
    "                c+=1\n",
    "        return l[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [1 for i in range(n)]\n",
    "        i,j,k = 0,0,0\n",
    "        for idx in range(1,n):\n",
    "            # ic = jc = kc =False\n",
    "            c1 = dp[i]*2 if dp[i]*2>dp[idx-1] else float('inf')\n",
    "            c2 = dp[j]*3 if dp[j]*3>dp[idx-1] else float('inf')\n",
    "            c3 = dp[k]*5 if dp[k]*5>dp[idx-1] else float('inf')\n",
    "            # c4 = dp[i]*3 if dp[i]*3>dp[idx-1] else float('inf')\n",
    "            # c5 = dp[j]*3 if dp[j]*3>dp[idx-1] else float('inf')\n",
    "            # c6 = dp[k]*3 if dp[k]*3>dp[idx-1] else float('inf')\n",
    "            # c7 = dp[i]*5 if dp[i]*5>dp[idx-1] else float('inf')\n",
    "            # c8 = dp[j]*5 if dp[j]*5>dp[idx-1] else float('inf')\n",
    "            # c9 = dp[k]*5 if dp[k]*5>dp[idx-1] else float('inf')\n",
    "            dp[idx] = min(c1,c2,c3)#,c4,c5,c6,c7,c8,c9)\n",
    "            if c1==dp[idx]  : i+=1\n",
    "            if c2==dp[idx] :j+=1\n",
    "            if c3==dp[idx] :k+=1\n",
    "\n",
    "            # i+= 1 if ic and ((jc and i<=j) or ( kc and i<=k ) or (not (jc or kc))) else 0\n",
    "            # j+= 1 if jc and ((kc and j<=k) or ( ic and j<=i ) or (not (ic or kc))) else 0\n",
    "            # k+= 1 if kc and ((jc and k<=j) or ( ic and k<=i ) or (not (jc or ic))) else 0\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n <= 6: return n\n",
    "        res = [0,1,2,3,4,5,6]\n",
    "        i2, i3, i5 = 4, 3, 2\n",
    "        for _ in range(7, n + 1):\n",
    "            tx = 2 * res[i2], 3 * res[i3], 5 * res[i5]\n",
    "            x = min(tx)\n",
    "            if x == tx[0]: i2 += 1\n",
    "            if x == tx[1]: i3 += 1\n",
    "            if x == tx[2]: i5 += 1\n",
    "            res.append(x)\n",
    "        return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] =1\n",
    "        p1=p2=p3=1\n",
    "        for i in range(2,n+1):\n",
    "            ans = min(dp[p1]*2,dp[p2]*3,dp[p3]*5)\n",
    "            dp[i] = ans\n",
    "            if dp[i] == dp[p1]*2:\n",
    "                p1+=1\n",
    "            if dp[i] == dp[p2]*3:\n",
    "                p2+=1\n",
    "            if dp[i] == dp[p3]*5:\n",
    "                p3+=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1] * n \n",
    "        idx2, idx3, idx5 = 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min(2 * dp[idx2], 3 * dp[idx3], 5 * dp[idx5])\n",
    "            idx2 += 1 if dp[i] == 2 * dp[idx2] else 0\n",
    "            idx3 += 1 if dp[i] == 3 * dp[idx3] else 0\n",
    "            idx5 += 1 if dp[i] == 5 * dp[idx5] else 0\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        a=[2,3,5]\n",
    "        b=[1,1,1]\n",
    "        c=[1]\n",
    "        d=[2,3,5]\n",
    "        for _ in range(n-1):\n",
    "            z=min(a)\n",
    "            c.append(z)\n",
    "            for i in range(3):\n",
    "                if a[i]==z:\n",
    "                    a[i]=d[i]*c[b[i]]\n",
    "                    b[i]+=1\n",
    "        return (c[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res,a,b,c=[1]*n,0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5=res[a]*2,res[b]*3,res[c]*5\n",
    "            res[i]=min(n2,n3,n5)\n",
    "            if n2==res[i]:a+=1\n",
    "            if n3==res[i]:b+=1\n",
    "            if n5==res[i]:c+=1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \n",
    "        ugly_numbers = [1]\n",
    "        i2,i3,i5 = 0,0,0\n",
    "        while len(ugly_numbers) < n:\n",
    "            next2 = ugly_numbers[i2] * 2\n",
    "            next3 = ugly_numbers[i3] * 3\n",
    "            next5 = ugly_numbers[i5] * 5\n",
    "\n",
    "            next_min = min(next2,next3,next5)\n",
    "            ugly_numbers.append(next_min)\n",
    "            if next_min == next2:\n",
    "                i2+=1\n",
    "            if next_min == next3:\n",
    "                i3+=1\n",
    "            if next_min == next5:\n",
    "                i5+=1\n",
    "\n",
    "        # print(ugly_numbers)\n",
    "        return ugly_numbers[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        table = []\n",
    "        que = []\n",
    "        heapq.heapify(que)\n",
    "        heapq.heappush(que,1)\n",
    "        while len(table) < n:\n",
    "            g = heapq.heappop(que)\n",
    "            table.append(g)\n",
    "            for i in 2,3,5:\n",
    "                ans = g*i\n",
    "                if ans not in que:\n",
    "                    heapq.heappush(que,ans)\n",
    "    \n",
    "        return table[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \n",
    "        ugly_numbers = [1]\n",
    "        i2,i3,i5 = 0,0,0\n",
    "\n",
    "        while len(ugly_numbers) < n:\n",
    "            n2,n3,n5 = ugly_numbers[i2]*2,ugly_numbers[i3]*3,ugly_numbers[i5]*5\n",
    "            nmin = min(n2,n3,n5)\n",
    "            ugly_numbers.append(nmin)\n",
    "            if nmin == n2:\n",
    "                i2 += 1\n",
    "            if nmin == n3:\n",
    "                i3 += 1\n",
    "            if nmin == n5:\n",
    "                i5 += 1\n",
    "        \n",
    "        return ugly_numbers[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ### 用还没乘过 2 的最小丑数乘以 2；用还没乘过 3 的最小丑数乘以 3；用还没乘过 5 的最小丑数乘以 5。然后在得到的数字中取最小，就是新的丑数。\n",
    "    #### 3 个指针 index2, index3, index5 分别表示丑数集合中还没乘过 2，3，5 的丑数位置。\n",
    "\n",
    "\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res,a,b,c=[1]*n,0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5=res[a]*2,res[b]*3,res[c]*5\n",
    "            res[i]=min(n2,n3,n5)\n",
    "            if res[i]==n2: a+=1\n",
    "            if res[i]==n3: b+=1\n",
    "            if res[i]==n5: c+=1\n",
    "        return res[-1]\n",
    "        # res, a, b, c = [1] * n, 0, 0, 0\n",
    "        # for i in range(1, n):\n",
    "        #     n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "        #     res[i] = min(n2, n3, n5)\n",
    "        #     if res[i] == n2: a += 1\n",
    "        #     if res[i] == n3: b += 1\n",
    "        #     if res[i] == n5: c += 1\n",
    "        # return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[1] = 1\n",
    "        p2, p3, p5 = 1, 1, 1\n",
    "        for i in range(2, n+1):\n",
    "            n2, n3, n5 = dp[p2]*2, dp[p3]*3, dp[p5]*5\n",
    "            dp[i] = min(n2, n3, n5)\n",
    "            if dp[i] == n2:\n",
    "                p2 += 1\n",
    "            if dp[i] == n3:\n",
    "                p3 += 1\n",
    "            if dp[i] == n5:\n",
    "                p5 += 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        ugly_numbers = [1]\n",
    "        i2 = i3 = i5 = 0\n",
    "\n",
    "        while len(ugly_numbers) < n:\n",
    "            next2 = ugly_numbers[i2] * 2\n",
    "            next3 = ugly_numbers[i3] * 3\n",
    "            next5 = ugly_numbers[i5] * 5\n",
    "\n",
    "            next_ugly = min(next2, next3, next5)\n",
    "            ugly_numbers.append(next_ugly)\n",
    "\n",
    "            if next_ugly == next2:\n",
    "                i2 += 1\n",
    "            if next_ugly == next3:\n",
    "                i3 += 1\n",
    "            if next_ugly == next5:\n",
    "                i5 += 1\n",
    "\n",
    "        return ugly_numbers[-1]\n",
    "\n",
    "# Testing the function with an example\n",
    "sol = Solution()\n",
    "sol.nthUglyNumber(10)  # Example: Find the 10th ugly number\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] =1\n",
    "        p1=p2=p3=1\n",
    "        for i in range(2,n+1):\n",
    "            ans = min(dp[p1]*2,dp[p2]*3,dp[p3]*5)\n",
    "            dp[i] = ans\n",
    "            if dp[i] == dp[p1]*2:\n",
    "                p1+=1\n",
    "            if dp[i] == dp[p2]*3:\n",
    "                p2+=1\n",
    "            if dp[i] == dp[p3]*5:\n",
    "                p3+=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "limit=1690\n",
    "uglyNums=[1]\n",
    "p2,p3,p5=0,0,0\n",
    "for i in range(limit - 1):\n",
    "    n2,n3,n5 = uglyNums[p2]*2,uglyNums[p3]*3,uglyNums[p5]*5\n",
    "    uglyNums.append(min(n2, n3, n5))\n",
    "    if n2 == uglyNums[-1]:\n",
    "        p2 += 1\n",
    "    if n3 == uglyNums[-1]:\n",
    "        p3 += 1\n",
    "    if n5 == uglyNums[-1]:\n",
    "        p5 += 1\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        return uglyNums[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        pq = [1]\n",
    "        s = set()\n",
    "        for i in range(n - 1):\n",
    "            tmp = heapq.heappop(pq)\n",
    "            for j in [2,3,5]:\n",
    "                if tmp * j not in s:\n",
    "                    heapq.heappush(pq, tmp * j)\n",
    "                    s.add(tmp * j)\n",
    "        return heapq.heappop(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        result=[1]\n",
    "        id2=id3=id5=0\n",
    "        for i in range(n-1):\n",
    "            result.append(min(result[id2]*2,result[id3]*3,result[id5]*5))\n",
    "            if result[-1]==2*result[id2]:\n",
    "                id2+=1\n",
    "            if result[-1]==3*result[id3]:\n",
    "                id3+=1\n",
    "            if result[-1]==5*result[id5]:\n",
    "                id5+=1\n",
    "        return result[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ans = [1]\n",
    "        for i in range(n):\n",
    "            for j in [2,3,5]:\n",
    "                if ans[i] * j not in ans:\n",
    "                    ans.append(ans[i] * j)\n",
    "            ans = sorted(ans)\n",
    "        return ans[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # 根据题意，每个丑数都可以由其他较小的丑数通过乘以2或3或5得到\n",
    "        # dp[i]表示第i个丑数\n",
    "        # dp[1] = 1\n",
    "        # 定义三个指针p2 p3 p5表示下一个丑数是当前指针指向的丑数乘以对应的质因数，初始时 三个指针都是1\n",
    "        # transition dp[1] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5) 比较dp[i]和dp[p2]*2, dp[p3]*3, dp[p5]*5是否相等，相等就将对应的指针+1\n",
    "\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5\n",
    "            dp[i] = min(num2, num3, num5)\n",
    "            # 看最小的数字是哪个，找到以后就把那个位置+1;相当于把每个位置都*2 *3 *5然后按照顺序排列\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min(2*dp[p2],3*dp[p3],5*dp[p5])\n",
    "            if dp[i] == 2*dp[p2]:p2+=1\n",
    "            if dp[i] == 3*dp[p3]:p3+=1\n",
    "            if dp[i] == 5*dp[p5]:p5+=1\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        p2=p3=p5=1\n",
    "        for i in range(2,n+1):\n",
    "            dp2=dp[p2]*2\n",
    "            dp3=dp[p3]*3\n",
    "            dp5=dp[p5]*5\n",
    "            Min=min(dp2,dp3,dp5)\n",
    "            dp[i]=Min\n",
    "            if dp2==Min:\n",
    "                p2+=1\n",
    "            if dp3==Min:\n",
    "                p3+=1\n",
    "            if dp5==Min:\n",
    "                p5+=1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [1]\n",
    "        a = b = c = 0\n",
    "        for _ in range(1, n):\n",
    "            num = min(res[a] * 2, res[b] * 3, res[c] * 5)\n",
    "            res.append(num)\n",
    "            if num == res[a] * 2:\n",
    "                a += 1\n",
    "            if num == res[b] * 3:\n",
    "                b += 1\n",
    "            if num == res[c] * 5:\n",
    "                c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [0] * (n+1)\n",
    "        res[0] = 1\n",
    "        i, j, k = 0, 0, 0\n",
    "        for idx in range(1, n):\n",
    "            t = min(res[i] * 2, res[j] * 3, res[k] * 5)\n",
    "            res[idx] = t\n",
    "            if t == res[i] * 2:\n",
    "                i += 1\n",
    "            if t == res[j] * 3:\n",
    "                j += 1\n",
    "            if t == res[k] * 5:\n",
    "                k += 1\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = {2,3,5}\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(n-1):\n",
    "            cur = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                n = cur * factor\n",
    "                if n not in seen:\n",
    "                    seen.add(n)\n",
    "                    heapq.heappush(heap, n)\n",
    "        \n",
    "        return heapq.heappop(heap)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        i,j,k=0,0,0\n",
    "\n",
    "        ugly_nums = []\n",
    "\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        ugly_nums.append(1)\n",
    "        \n",
    "        for _ in range(1, n):\n",
    "            t2 = ugly_nums[i]*2\n",
    "            t3 = ugly_nums[j]*3\n",
    "            t5 = ugly_nums[k]*5\n",
    "\n",
    "            tmp = min(t2, t3, t5)\n",
    "            ugly_nums.append(tmp)\n",
    "            \n",
    "            if tmp == t2:\n",
    "                i += 1\n",
    "            \n",
    "            if tmp == t3:\n",
    "                j += 1\n",
    "            \n",
    "            if tmp == t5:\n",
    "                k += 1\n",
    "\n",
    "        return ugly_nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ret, a, b, c = [1] * n, 0, 0, 0\n",
    "        num = [2, 3, 5]\n",
    "        for i in range(1, n):\n",
    "            n1 = num[0] * ret[a]\n",
    "            n2 = num[1] * ret[b]\n",
    "            n3 = num[2] * ret[c]\n",
    "            ret[i] = min(n1, n2, n3)\n",
    "            if ret[i] == n1:\n",
    "                a += 1\n",
    "            if ret[i] == n2:\n",
    "                b += 1\n",
    "            if ret[i] == n3:\n",
    "                c += 1\n",
    "        return ret[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res, a, b, c = [1] * n, 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        return res[-1]\n",
    "\n",
    "# 作者：Krahets\n",
    "# 链接：https://leetcode.cn/problems/ugly-number-ii/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        table = [1]\n",
    "        que = []\n",
    "        heapq.heapify(que)\n",
    "        heapq.heappush(que,1)\n",
    "        while len(table) < n*2:\n",
    "            g = heapq.heappop(que)\n",
    "            for i in 2,3,5:\n",
    "                ans = g*i\n",
    "                if ans not in table:\n",
    "                    table.append(ans)\n",
    "                    heapq.heappush(que,ans)\n",
    "        table.sort()\n",
    "        return table[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 最小堆+哈希\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = [2, 3, 5]\n",
    "        seen = {1}\n",
    "        pq = [1]\n",
    "        for _ in range(n - 1):\n",
    "            curr = heapq.heappop(pq)\n",
    "            for factor in factors:\n",
    "                next = curr * factor\n",
    "                if next not in seen:\n",
    "                    seen.add(next)\n",
    "                    heapq.heappush(pq, next)\n",
    "        return heapq.heappop(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "\n",
    "        res = [1]\n",
    "        seen = set()\n",
    "        seen.add(1)\n",
    "\n",
    "        heap = [1]\n",
    "        res = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            res = heapq.heappop(heap)\n",
    "            print(res)\n",
    "\n",
    "            n2 = res * 2\n",
    "            if n2 not in seen:\n",
    "                heapq.heappush(heap, n2)\n",
    "                seen.add(n2)\n",
    "            n3 = res * 3\n",
    "            if n3 not in seen:\n",
    "                heapq.heappush(heap, n3)\n",
    "                seen.add(n3)\n",
    "            n5 = res * 5\n",
    "            if n5 not in seen:\n",
    "                heapq.heappush(heap, n5)\n",
    "                seen.add(n5)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ugly = [1, ]\n",
    "        seen = set([1])\n",
    "        factors = [2, 3, 5]\n",
    "        cur = 1\n",
    "        for i in range(n):\n",
    "            cur = heapq.heappop(ugly)\n",
    "            for f in factors:\n",
    "                new = cur * f\n",
    "                if new not in seen:\n",
    "                    seen.add(new)\n",
    "                    heapq.heappush(ugly, new)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "\n",
    "\n",
    "        ans = [1]\n",
    "        index = 0\n",
    "        map1 = {}\n",
    "        map1[1] = 1\n",
    "\n",
    "        while index < n:\n",
    "\n",
    "            \n",
    "            map1[ans[index]*2] =1 if ans[index]*2 in map1 else ans.append(ans[index]*2)\n",
    "\n",
    "           \n",
    "            map1[ans[index]*3] =1 if ans[index]*3 in map1 else ans.append(ans[index]*3)\n",
    "\n",
    "            map1[ans[index]*4] =1 if ans[index]*4 in map1 else ans.append(ans[index]*4)\n",
    "\n",
    "            \n",
    "            map1[ans[index]*5] =1 if ans[index]*5 in map1 else ans.append(ans[index]*5)\n",
    "\n",
    "            index +=1\n",
    "            ans.sort()\n",
    "\n",
    "        return ans[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        seen = {1}\n",
    "        hq = [1]\n",
    "        factors = [2, 3, 5]\n",
    "        for _ in range(n-1):\n",
    "            cur = heappop(hq)\n",
    "            for factor in factors:\n",
    "                if (nxt:= factor * cur) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heappush(hq, nxt)\n",
    "        return heappop(hq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n <= 6: return n\n",
    "        tmp = {1,2,3,4,5,6}\n",
    "        res = [0,1,2,3,4,5,6]\n",
    "        x = [4, 3, 2]\n",
    "        for _ in range(7, n + 1):\n",
    "            while True:\n",
    "                tx = 2 * res[x[0]], 3 * res[x[1]], 5 * res[x[2]]\n",
    "                resx = min(tx)\n",
    "                x[tx.index(resx)] += 1\n",
    "                if resx in tmp:\n",
    "                    continue\n",
    "                tmp.add(resx)\n",
    "                res.append(resx)\n",
    "                break\n",
    "              \n",
    "        return resx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = [2, 3, 5]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "        factors = [2,3,5]\n",
    "        for i in range(n-1):\n",
    "            cur = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if cur*factor not in seen:\n",
    "                    seen.add(cur*factor)\n",
    "                    heapq.heappush(heap,cur*factor)\n",
    "        \n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "\n",
    "        heap = []\n",
    "        res = []\n",
    "        seen = set([1, 2, 3, 5])\n",
    "\n",
    "        heapq.heappush(heap, 1)\n",
    "        heapq.heappush(heap, 2)\n",
    "        heapq.heappush(heap, 3)\n",
    "        heapq.heappush(heap, 5)\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            num = heapq.heappop(heap)\n",
    "            res.append(num)\n",
    "\n",
    "            if num * 2 not in seen:\n",
    "                seen.add(num * 2)\n",
    "                heapq.heappush(heap, num * 2)\n",
    "            if num * 3 not in seen:\n",
    "                seen.add(num * 3)\n",
    "                heapq.heappush(heap, num * 3)\n",
    "            if num * 5 not in seen:\n",
    "                seen.add(num * 5)\n",
    "                heapq.heappush(heap, num * 5)\n",
    "        \n",
    "        return res[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ugly = [1]\n",
    "        factor = [2, 3, 5]\n",
    "        i = 1\n",
    "        s = set()\n",
    "        while i < n:\n",
    "            front = heappop(ugly)\n",
    "            for f in factor:\n",
    "                if not f * front in s:\n",
    "                    s.add(f * front)\n",
    "                    heappush(ugly, front * f)\n",
    "            i += 1\n",
    "        return heappop(ugly)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        arr = [1]\n",
    "        factors = [2,3,4,5]\n",
    "        _set = set()\n",
    "        for i in range(n-1):\n",
    "            v = heapq.heappop(arr)\n",
    "            for f in factors:\n",
    "                num = v * f\n",
    "                if num not in _set:\n",
    "                    _set.add(num)\n",
    "                    heapq.heappush(arr, num)\n",
    "        return heapq.heappop(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:return 1\n",
    "        res = [1]\n",
    "        heapq.heapify(res)\n",
    "        helset = {1}\n",
    "        \n",
    "        for _ in range(n-1):\n",
    "            cur = heapq.heappop(res)\n",
    "            tem =[cur * 3,cur * 5, cur*2]\n",
    "            for k in tem:\n",
    "                if k not in helset:\n",
    "                    helset.add(k)\n",
    "                    heapq.heappush(res,k)\n",
    "            # if tem not in helset:\n",
    "            #     heapq.heappush(res,tem)\n",
    "            #     helset.add(tem)\n",
    "            # tem = res[i] * 3\n",
    "            # if len(res)<=n and tem not in helset:\n",
    "            #     heapq.heappush(res,tem)\n",
    "            #     helset.add(tem)\n",
    "            # tem = res[i] * 5\n",
    "            # if len(res)<=n and tem not in helset:\n",
    "            #     heapq.heappush(res,tem)\n",
    "            #     helset.add(tem)\n",
    "            # i+=1\n",
    "        \n",
    "        return heapq.heappop(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        base = [2, 3, 5]\n",
    "        seen = {1}  # already exist in the heap\n",
    "        heap = [1]  # to create a heap\n",
    "        for i in range(n-1):\n",
    "            min = heapq.heappop(heap)\n",
    "            seen.add(min)\n",
    "            for fact in base:\n",
    "                if (nxt := fact * min) in seen:\n",
    "                    continue\n",
    "                heapq.heappush(heap, nxt)\n",
    "                seen.add(nxt)\n",
    "        return heapq.heappop(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "解法一:优先队列\n",
    "\n",
    "每次从队列中取出最小值x\n",
    "将x分别和2/3/5相乘的结果入对，若是已经入队过，就不需要再次入队了。\n",
    "取出的第n次直接返回，\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # 丑数的三个质因子\n",
    "        nums = [2, 3, 5]\n",
    "        # 记录已经入队的丑数\n",
    "        seen = {1}\n",
    "        # 初始化队列，第一个丑数是1\n",
    "        pq = [1]\n",
    "        # 从1开始，遍历n次\n",
    "        for i in range(1, n + 1):\n",
    "            # 每次从队列中取出最小数\n",
    "            x = heapq.heappop(pq)\n",
    "            # 第n次返回\n",
    "            if i == n:\n",
    "                return x\n",
    "            else:\n",
    "                # 将每次取出的丑数与质因子相乘\n",
    "                for num in nums:\n",
    "                    t = num * x\n",
    "                    # 将没有出现过的丑数入队\n",
    "                    if t not in seen:\n",
    "                        seen.add(t)\n",
    "                        heapq.heappush(pq, t)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        l=[1]\n",
    "        a,b,c=0,0,0\n",
    "        for i in range(1,n):\n",
    "            la,lb,lc=l[a]*2,l[b]*3,l[c]*5\n",
    "            t=min(la,lb,lc)\n",
    "            l.append(t)\n",
    "            if t==la: a+=1\n",
    "            if t==lb: b+=1\n",
    "            if t==lc: c+=1\n",
    "        print(l)\n",
    "        return l[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        heap = []\n",
    "        heapq.heappush(heap,1)\n",
    "\n",
    "        ug = 1\n",
    "        factors = {2,3,5}\n",
    "        seen = set()\n",
    "\n",
    "        res = []\n",
    "        for i in range(1699):\n",
    "            ug = heappop(heap)\n",
    "            res.append(ug)\n",
    "            for factor in factors:\n",
    "                if ug*factor not in seen:\n",
    "                    seen.add(ug*factor)\n",
    "                    heapq.heappush(heap,ug*factor)\n",
    "        \n",
    "        return res[n-1]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        c = set()\n",
    "        m = 1\n",
    "        stack = [1]\n",
    "        d = []\n",
    "        while len(d) < n:\n",
    "            m = min(stack)\n",
    "            stack.remove(m)\n",
    "            d.append(m)\n",
    "            if m * 2 not in c:\n",
    "                stack.append(m * 2)\n",
    "                c.add(m * 2)\n",
    "            if m * 3 not in c:\n",
    "                stack.append(m * 3)\n",
    "                c.add(m * 3)\n",
    "            if m * 5 not in c:\n",
    "                stack.append(m * 5)\n",
    "                c.add(m * 5)\n",
    "        return d[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        choushu=[2,3,5]\n",
    "        chouset=set()\n",
    "        for i in range(500):\n",
    "            for j in range(i+1):\n",
    "                a=choushu[i]*choushu[j]\n",
    "                if a not in chouset:\n",
    "                    choushu.append(a)\n",
    "                    chouset.add(a)\n",
    "        choushu=[1]+sorted(choushu)\n",
    "        return choushu[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        hash = defaultdict(int)\n",
    "        q = SortedList()\n",
    "        q.add(1)\n",
    "        hash[1] = 1\n",
    "        f = [2,3,5]\n",
    "        for i in range(1 ,n+1):\n",
    "            # print(\"___\", q,)\n",
    "            ele = q.pop(0)\n",
    "            if i == n:\n",
    "                return ele\n",
    "            for j in range(0,3):\n",
    "                next_ele = ele * f[j]\n",
    "                # print(\"next_ele : \", next_ele)\n",
    "                if hash[next_ele] == 0:\n",
    "                    hash[next_ele] = 1\n",
    "                    q.add(next_ele)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# /**\n",
    "#  * @param {number} n\n",
    "#  * @return {boolean}\n",
    "#  */\n",
    "# var nthUglyNumber = function(n) {\n",
    "#     if(n===1) return 1\n",
    "#     const hash = {}\n",
    "#     const queue= new MinPriorityQueue()\n",
    "#     queue.enqueue(1)\n",
    "#     hash[1] = true\n",
    "#     const f = [2,3,5]\n",
    "#     // let num = undefined\n",
    "#     for(let i=1; i<=n; i++) {\n",
    "#         const num = queue.dequeue().priority\n",
    "#         // console.log(queue.toArray())\n",
    "#         if(i===n) return num\n",
    "#         for(let j=0; j<3;j++) {\n",
    "#             const next = num * f[j]\n",
    "#             if(!hash[next]) {\n",
    "#                 hash[next] = true\n",
    "#                 queue.enqueue(next)\n",
    "#             }\n",
    "#         }\n",
    "#     }\n",
    "# };"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        \"\"\" 使用最小堆heapq\n",
    "        \"\"\"\n",
    "\n",
    "        import heapq\n",
    "\n",
    "        num_set = set()\n",
    "        num_set.add(1)\n",
    "        trace_list = [1]\n",
    "        heapq.heapify(trace_list)\n",
    "        smallest_ugly = 1\n",
    "\n",
    "        i = 0\n",
    "        while i != n:\n",
    "            smallest_ugly = heapq.heappop(trace_list)\n",
    "            print(smallest_ugly)\n",
    "            if smallest_ugly*2 not in num_set:\n",
    "                num_set.add(smallest_ugly*2)\n",
    "                heapq.heappush(trace_list, smallest_ugly*2)\n",
    "            if smallest_ugly*3 not in num_set:\n",
    "                num_set.add(smallest_ugly*3)\n",
    "                heapq.heappush(trace_list, smallest_ugly*3)\n",
    "            if smallest_ugly*5 not in num_set:\n",
    "                num_set.add(smallest_ugly*5)\n",
    "                heapq.heappush(trace_list, smallest_ugly*5)\n",
    "            i += 1\n",
    "        return smallest_ugly\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        b = [2,3,5]\n",
    "        s = {2,3,5}\n",
    "        heapq.heapify(b)\n",
    "        n-=1\n",
    "        a=0\n",
    "        while n>0:\n",
    "            a=heapq.heappop(b)\n",
    "            if a*2 not in s:\n",
    "                s.add(a*2)\n",
    "                heapq.heappush(b,a*2)\n",
    "            if a*3 not in s:\n",
    "                s.add(a*3)\n",
    "                heapq.heappush(b,a*3)\n",
    "            if a*5 not in s:\n",
    "                s.add(a*5)\n",
    "                heapq.heappush(b,a*5)\n",
    "            n-=1\n",
    "            print(a)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp=[0,1]\n",
    "        p2=p3=p5=1\n",
    "        i=0\n",
    "        while len(dp)<n+1:\n",
    "            num2=2*dp[p2]\n",
    "            num3=3*dp[p3]  \n",
    "            num5=5*dp[p5]\n",
    "            i=min(num2,num3,num5)\n",
    "            if num2==i:\n",
    "                p2+=1\n",
    "            if num3==i:\n",
    "                p3+=1\n",
    "            if num5==i:\n",
    "                p5+=1\n",
    "            dp.append(i)\n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ans = []\n",
    "        for i in range(14):\n",
    "            for j in range(21):\n",
    "                for k in range(35):\n",
    "                    a = (5 ** i )* (3 ** j )* (2 ** k)\n",
    "                    ans.append(a)\n",
    "        ans = sorted(ans)\n",
    "        return ans[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]\n",
    "        f = [2, 3, 5]\n",
    "        res = {1}\n",
    "        for i in range(n):\n",
    "            temp = min(dp)\n",
    "            dp.remove(temp)\n",
    "            for j in f:\n",
    "                dp.append(j*temp)\n",
    "                res.add(j*temp)\n",
    "            dp = list(set(dp))\n",
    "        res = sorted(list(res))\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ret = None\n",
    "        h = []\n",
    "        ans_set = set()\n",
    "        n2,n3,n5=0,0,0\n",
    "        heapq.heappush(h,(pow(2,n2)*pow(3,n3)*pow(5,n5),n2,n3,n5))\n",
    "        while n>0:\n",
    "            hr = heapq.heappop(h)\n",
    "            ret=hr[0]\n",
    "            if (hr[1]+1,hr[2],hr[3]) not in ans_set:\n",
    "                ans_set.add((hr[1]+1,hr[2],hr[3]))\n",
    "                heapq.heappush(h,(pow(2,hr[1]+1)*pow(3,hr[2])*pow(5,hr[3]),hr[1]+1,hr[2],hr[3]))\n",
    "            if (hr[1],hr[2]+1,hr[3]) not in ans_set:\n",
    "                ans_set.add((hr[1],hr[2]+1,hr[3]))\n",
    "                heapq.heappush(h,(pow(2,hr[1])*pow(3,hr[2]+1)*pow(5,hr[3]),hr[1],hr[2]+1,hr[3]))\n",
    "            if (hr[1],hr[2],hr[3]+1) not in ans_set:\n",
    "                ans_set.add((hr[1],hr[2],hr[3]+1))\n",
    "                heapq.heappush(h,(pow(2,hr[1])*pow(3,hr[2])*pow(5,hr[3]+1),hr[1],hr[2],hr[3]+1))\n",
    "            n-=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [1]\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            temp_a,temp_b,temp_c = res[a]*2, res[b]*3, res[c]*5\n",
    "            min_val = min(temp_a,temp_b,temp_c)\n",
    "            if min_val == temp_a:\n",
    "                a += 1\n",
    "            if min_val == temp_b:\n",
    "                b += 1\n",
    "            if min_val == temp_c:\n",
    "                c += 1\n",
    "            res.append(min_val)\n",
    "        print(res)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        pointer = [0, 0, 0]\n",
    "        num = [1]\n",
    "        for _ in range(n):\n",
    "            next = [num[pointer[0]] * 2, num[pointer[1]] * 3, num[pointer[2]] * 5]\n",
    "            ans = min(next)\n",
    "            num.append(ans)\n",
    "            for i in range(3):\n",
    "                if next[i] == ans:\n",
    "                    pointer[i] += 1\n",
    "        print(num)          \n",
    "        return num[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            dp[i] = min(dp[p2]*2,dp[p3]*3,dp[p5]*5)\n",
    "            if dp[p2]*2 == dp[i]: \n",
    "                p2 += 1\n",
    "            if dp[p3]*3 == dp[i]: \n",
    "                p3 += 1\n",
    "            if dp[p5]*5 == dp[i]: \n",
    "                p5 += 1\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
